P3130 Counting Haybale P

• 'P' l r k，区间加 $k$
• 'M' l r，求区间最小值
• 'S' l r，求区间和

Same Problem
Circular RMQ - 洛谷 | 计算机科学教育新生态

Solution

线段树

主要是求区间最小值。

#define lc u<<1
#define rc u<<1|1
int a[200010];
struct Tree { //线段树
    ll l, r, sum, add, min;
}tr[800010];

void pushup(ll u) { //上传
    tr[u].sum = tr[lc].sum + tr[rc].sum;
    tr[u].min = min(tr[lc].min, tr[rc].min);
}
void pushdown(ll u) { //下传
    if (tr[u].add) {
        tr[lc].sum += tr[u].add * (tr[lc].r - tr[lc].l + 1);
        tr[rc].sum += tr[u].add * (tr[rc].r - tr[rc].l + 1);
        tr[lc].add += tr[u].add;
        tr[rc].add += tr[u].add;
        tr[lc].min += tr[u].add;
        tr[rc].min += tr[u].add;
        tr[u].add = 0;
    }
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l],0,a[l]};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        tr[u].add += k;
        tr[u].min += k;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) change(lc, l, r, k);
    if (r > m) change(rc, l, r, k);
    pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    ll sum = 0;
    if (l <= m) sum += query(lc, l, r);
    if (r > m) sum += query(rc, l, r);
    return sum;
}
ll querymin(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].min;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    ll ans = INTMAX_MAX;
    if (l <= m) ans = min(ans, querymin(lc, l, r));
    if (r > m) ans = min(ans, querymin(rc, l, r));
    return ans;
}

void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> a[i];
    build(1, 1, n);
    while (m--) {
        char op;cin >> op;
        int l, r;cin >> l >> r;
        if (op == 'P') {
            int k;cin >> k;change(1, l, r, k);
        } else if (op == 'M') {
            cout << querymin(1, l, r) << '\n';
        } else {
            cout << query(1, l, r) << "\n";
        }
    }
}